\documentclass[12pt, a4paper,english,spanish]{article}
\usepackage{babel}
%\parindent = 10 pt
%\parskip = 11 pt
\usepackage[width=15.5cm, left=3cm, top=2.5cm, height= 24.5cm]{geometry}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage[latin1]{inputenc}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{tikz}
\usetikzlibrary{shadows}
\tikzset{>=latex}

\begin{document}
\shorthandoff{>}
\renewcommand{\refname}{} 

\begin{center}
\large{\textbf{Algoritmos y Estructuras de Datos III}}

\normalsize{Segundo Cuatrimestre de 2012}

\vspace{2mm}

Departamento de Computaci\'on\\
Facultad de Ciencias Exactas y Naturales\\
Universidad de Buenos Aires\\

\vspace{10mm}

\LARGE{\textsc{\textbf{Trabajo Pr\'actico 3}}} \\

\LARGE{Grupo 5}

\vspace{10mm}

\normalsize

\begin{tabular}{c|c|c}
\hline
\textbf{Autor} & \textbf{Correo electr\'onico} & \textbf{LU}\\
\hline
Emilio Ferro & reclarinette2002@yahoo.com.ar& 441$/$00\\    
Marina A. Niikado & mariniik@yahoo.com.ar & 711$/$07\\
Franco Pistasoli & fpistasoli@gmail.com & 194$/$08\\
Ezequiel Schwab & ezequiel.schwab@gmail.com & 132$/$09\\
\hline
\end{tabular}

\end{center}

\vskip 12pt
\rule{\textwidth}{1.2pt}
\vskip 5pt


\newpage

\setcounter{tocdepth}{2}  % para que aparezcan las subsecciones, ademas sacarle el * de la \subsection*{...}
\tableofcontents


\newpage

\section{Introducci\'on}
En este trabajo pr\'actico se presentar\'an distintos algoritmos para resolver el problema 2-TSP. \'Este consiste en encontrar en un grafo completo G dado y un nodo v perteneciente a G, dos ciclos que cubran todos los nodos del grafo y que s\'olo coincidan en $v$. G cuenta con un m\'inimo de cinco nodos y longitudes positivas asociadas a sus ejes. 

Se podr\'ia usar 2-TSP para modelar el problema de trazar una ruta de transporte.
Se tienen 2 veh\'iculos que tienen que pasar por cierta cantidad de ciudades. No pueden quedar ciudades sin recorrer y cada ciudad s\'olo puede ser visitada una vez, salvo la ciudad de partida que se visita 2 veces (en el inicio y final del recorrido). Ambos veh\'iculos parten de la ciudad c (en la \'unica que coinciden) y deben retornar a esta ciudad cuando terminen su recorrido. El costo total de ambos recorridos tiene que ser m\'inimo. Ir de una ciudad a otra tiene un costo fijo conocido. 
% ver si lo va o lo borramos...
Un ejemplo parecido ser\'ia el de tener una l\'inea de colectivos, la cual tiene 2 ramales. Las paradas correspondientes a esta l\'inea ya est\'a fijada. Lo que se tiene que decidir es cu\'al parada corresponder\'a a un ramal u otro, pasando por todas las paradas de la l\'inea y haciendo el recorrido lo m\'as r\'apido posible. Ambos ramales comienzan y terminan su recorrido en la terminal y s\'olo se cruzan en este punto. 


\section{Desarrollo}
El problema 2-TSP se resolver\'a mediante un algoritmo exacto, otros heur\'isticos y un metaheur\'istico. La raz\'on por la cual se proveen heur\'isticas para este problema es que no se conocen a\'un (o por lo menos nosotros no conocemos) algoritmos polinomiales capaces de resolverlo de tal forma de obtener siempre la soluci\'on \'optima. En casos como \'este, donde el problema es dif\'icil de resolver, un algoritmo exacto tendr\'ia una complejidad exponencial, lo que lo vuelve inutilizable. En cambio, una heur\'istica resolver\'ia el problema en un tiempo razonable, sin garantizar que encontrar\'a la soluci\'on exacta, pero una aproximada.

Una metaheur\'istica usa t\'ecnicas heur\'isticas con el prop\'osito de mejorar una soluci\'on candidata, en forma iterativa, hasta llegar a una que ya no puede ser mejorada, y retorna esta \'ultima. De todas maneras tampoco garantiza que la soluci\'on retornada sea la \'optima, pero se aproximar\'a a \'esta. En este trabajo implementaremos una metaheur\'istica conocida como B\'usqueda Tab\'u.

El m\'etodo de Java que resuelve el problema, para cada algoritmo, se llama \texttt{get2TSP()}.   

\subsection{Algoritmo exacto}
\subsubsection*{Algoritmo propuesto}
El algoritmo exacto que implementamos para resolver 2-TSP devuelve la soluci\'on \'optima, o sea retorna los dos circuitos simples del grafo del problema tales que cubren todos sus nodos, coinciden s\'olo en un v\'ertice dado $v$, y su peso total es el m\'inimo de entre todos los posibles circuitos con estas caracter\'isticas. Llamaremos \textit{particion 2-TSP(v)} del grafo completo simple no dirigido $G = (V,X)$, con $|V| \geq 5$ a un conjunto formado por dos subgrafos inducidos por $V(G)$ (y por lo tanto completos), sean $G_1 = (V_1,X_1)$ y $G_2 = (V_2,X_2)$, tales que $V_1 \cap V_2 = \{v\}$ (con $v \in V$), $V_1 \cup V_2 = V$, $X_1 \cap X_2 = \emptyset$, y $X_1$ y $X_2$ contienen, respectivamente, todas las aristas que son incidentes a los v\'ertices de $G_1$ y $G_2$ en el grafo $G$.      

A grandes rasgos, el algoritmo exacto realiza lo siguiente:

\begin{verbatim}
algoritmo get2TSP(Grafo G, Nodo v)
1.  Inicializar la variable pesoMinimoTotal en infinito
2.  Asignarle el conjunto vacio a la variable solucionFinal
3.  Para cada particion 2-TSP(v) de G, sea (G1,G2), hacer:
4.     Sea p1 el peso del circuito G1, y p2 el peso del circuito G2 
5.     pesoTotal = p1 + p2
6.     Si pesoTotal < pesoMinimoTotal 
7.        solucionFinal = (G1,G2)
8.        pesoMinimoTotal = pesoTotal
9.     FinSi
10. FinPara 
11. Devolver solucionFinal
12. Parar             
\end{verbatim} 

Para encontrar cada posible particion 2-TSP(v) de $G$, tuvimos que razonar un poco.

En principio sabemos que, para un grafo $G = (V,X)$ completo simple no dirigido de al menos 5 v\'ertices y con pesos positivos en los ejes, las particiones que podemos lograr tendr\'an exactamente dos circuitos de $i$ y $j$ nodos (incluyendo a $v$), respectivamente, donde $i+j=n+1$, con $n = |V|$ y $3 \leq i,j \leq n-2$. Entonces lo que tenemos que ver son todas las posibles maneras de sumar $n+1$ con estas restricciones sobre $i$ y $j$. Por ejemplo, para $n=10$, los pares $(i,j)$ posibles son (3,8); (4,7); (5,6); (6,5); (7,4); (8,3). %Ya veremos que con hallar s\'olo las tres primeras particiones (para este caso) alcanza.

Entonces, una vez que hallamos una partici\'on posible $(G_1,G_2)$, lo que hacemos es considerar todos los ciclos distintos que se pueden formar en $G$ con los v\'ertices de cada $G_i$, y combinamos un ciclo de $G_1$ con otro de $G_2$. Para cada combinaci\'on de ciclos, obtenemos la suma de sus pesos, y si este valor es menor que el calculado para la combinaci\'on que hasta el momento ten\'ia peso total m\'inimo, entonces asignamos esta nueva combinaci\'on a la variable \texttt{solucionFinal} y ahora el peso m\'inimo total pasa a ser la suma de los pesos de estos ciclos.

El algoritmo termina cuando se encuentra un par de ciclos, con las caracter\'isticas ya descriptas, que minimiza la suma de los pesos de cualquier otro par posible de circuitos en $G$.

Respecto de la correctitud del algoritmo exacto, lo que habr\'ia que justificar es que se logran obtener todos los posibles pares de circuitos simples de $G$ que coincidan s\'olo en $v$ y que cubran todos sus nodos. Ya vimos que esto sucede por la forma en que se van construyendo las combinaciones de circuitos, ya que se prueba con todas las formas de recorrer los nodos de cada $G_i$.

\subsubsection*{Complejidad}
En esta secci\'on se presenta un an\'alisis de la complejidad del algoritmo \texttt{get2TSP()} de la clase \texttt{Exacto}. Veremos m\'as adelante que tanto el peor como el mejor caso tendr\'an la misma complejidad.

El c\'odigo Java de \texttt{get2TSP()} es el siguiente: 

\newpage

\begin{footnotesize}
\texttt{public Solucion get2TSP()}

\begin{algorithmic}[1]
\State $int \; n = g.getN(); $ \Comment{$\mathcal{O}(1)$}
\State $int \; i = 3;$\Comment{$\mathcal{O}(1)$}
\State $int \; tam\_part1 = n + 1 - i, \; tam\_part2 = 3;$ 	\Comment{$\mathcal{O}(1)$}	
\State $int \; costoMinTotal = Integer.MAX\_VALUE; $ \Comment{$\mathcal{O}(1)$}			
\State $Solucion \; solFinal = null; $ 	\Comment{$\mathcal{O}(1)$}		
\While{$(tam\_part1 \geq tam\_part2)$} 
	\State $ArrayList<Integer> \; sol\_parcial = new \; ArrayList<Integer>(); $ \Comment{$\mathcal{O}(1)$}				
	\State $sol\_parcial.add(g.getOrig()); $ \Comment{$\mathcal{O}(1)$}	 %O(1) porq cuando lo agrega, el arreglo esta vacio
	\State $Solucion \; s\_part = solucion\_particion(tam\_part1, sol\_parcial); $	
	\State $int \; costoTotal = s\_part.getCosto();  $\Comment{$\mathcal{O}(1)$} 				
 	\If{$(costoTotal < costoMinTotal)$}\Comment{$\mathcal{O}(1)$}
		\State $solFinal = s\_part; $ 	\Comment{$\mathcal{O}(1)$}			
		\State $costoMinTotal = costoTotal;$ 	\Comment{$\mathcal{O}(1)$}	
		\State $costoMin = costoTotal; $ 	\Comment{$\mathcal{O}(1)$}			
    \EndIf
	\State $i++;$ 		\Comment{$\mathcal{O}(1)$}		
	\State $tam\_part1 = n + 1 - i;$ \Comment{$\mathcal{O}(1)$}		
	\State $tam\_part2 = i; $ 	\Comment{$\mathcal{O}(1)$}		
\EndWhile
\State $return \; solFinal; $ 	
\end{algorithmic}
\end{footnotesize}

$\newline$

El c\'odigo del m\'etodo recursivo \texttt{solucion\_particion} es \'este: \\

\begin{footnotesize}
\texttt{private Solucion solucion\_particion(int tam\_part1,}\\
\hspace*{8.4cm}\texttt{ArrayList<Integer> solucion\_parcial)}

\begin{algorithmic}[1]
\State $int \; n = g.getN(); $ \Comment{$\mathcal{O}(1)$}
\State $int \; nodo\_orig = g.getOrig();$	\Comment{$\mathcal{O}(1)$}	
\If{$(solucion\_parcial.size() == tam\_part1)$}	\Comment{$\mathcal{O}(1)$}
	\State $ArrayList<Integer> \; solucion\_parcial2 = g.getComplemento(solucion\_parcial); $		
	\State	$	solucion\_nueva.add(nodo\_orig);$
	\State	$	complemento.remove((Object) nodo\_orig);$
	\State	$	solucion\_parcial2 = mejorSolucion(tam\_part2, complemento,solucion\_nueva); $
	\State $int \; costo = g.calcular\_costo(solucion\_parcial) + g.calcular\_costo(solucion\_parcial2) $
	\If{$(costo < costoMin)$}	\Comment{$\mathcal{O}(1)$}
		\State $sol = new \; Solucion(solucion\_parcial,solucion\_parcial2,costo); $	\Comment{$\mathcal{O}(|solucion\_parcial|)$} %como tiene q usar clone, tarda esto				
		\State $// \; NUEVA \; SOLUCION$				
		\State $costoMin = costo;$			\Comment{$\mathcal{O}(1)$}		
	\EndIf
\Else{
\For{$(int \; i = 1; i \leq n; i++)$}
	\If{$(i \neq  nodo\_orig \; \land \; !solucion\_parcial.contains(i))$} \Comment{$\mathcal{O}(|solucion\_parcial|)$}
		\State $solucion\_parcial.add(i); $		\Comment{$\mathcal{O}(1)$}	
		\State $solucion\_particion(tam\_part1, solucion\_parcial); $			
		\State $solucion\_parcial.remove((Object) \; i);$	\Comment{$\mathcal{O}(1)$}				
	\EndIf
\EndFor
}
\EndIf
		
\State $return \; sol;$
\end{algorithmic}

\end{footnotesize}

$\newline$

\small{\textbf{Explicaci\'on de la complejidad de \texttt{solucion\_particion}}}

Las l\'ineas que tienen complejidad $\mathcal{O}(1)$ corresponden a asignaciones y/o comparaciones de tiempo constante, excepto en la l\'inea 17, donde se llama al m\'etodo \texttt{add} de la clase \textsc{ArrayList}, que toma tiempo constante (amortizado)\cite{java}. 

Las l\'ineas 10 y 16 toman tiempo lineal en la cantidad de elementos que tiene \textit{solucion\_parcial}. En el primer caso se llama al m\'etodo \texttt{clone()} en el constructor del nuevo objeto creado de tipo \textsc{Solucion}, el cual crea una copia de un objeto de tipo \textsc{ArrayList}. En el segundo caso se llama a los m\'etodos \texttt{contains} y \texttt{remove} de la clase \textsc{ArrayList}; el primero toma tiempo lineal en $|solucion\_parcial|$, mientras que el segundo es constante, ya que siempre se elimina elementos del final del arreglo. 

Por otro lado, en la l\'inea 4 se llama a un m\'etodo, \texttt{getComplemento}, el cual toma un arreglo redimensionable de tama\~no $|solucion\_parcial|$ y devuelve otro de tama\~no $n - |solucion\_parcial| + 1$, siendo $n$ la cantidad de v\'ertices del grafo $g$. Este arreglo contiene el primer elemento del arreglo de entrada seguido de todos los valores del conjunto $\{1, 2, \ldots , n\}$ tales que no pertenezcan a este arreglo. Luego, por cada valor de $1$ a $n$ se llama a \texttt{contains}, que toma tiempo lineal en la cantidad de elementos del arreglo $|solucion\_parcial|$. Por lo tanto, esta l\'inea toma tiempo $\mathcal{O}(n * |solucion\_parcial|)$ 

En la l\'inea 8 se llama al m\'etodo \texttt{calcular\_costo} de \textsc{Grafo}, el cual recorre el arreglo de entrada linealmente y realiza operaciones constantes por cada elemento visitado. Luego, la l\'inea 8 toma $\mathcal{O}(|solucion\_parcial| + |solucion\_parcial2|) = \mathcal{O}(n+1) =  \mathcal{O}(n)$, ya que al ser uno de estos arreglos el complemento del otro, su uni\'on contiene todos los nodos del grafo. 

Ahora s\'olo nos queda ver lo m\'as interesante de la complejidad de este algoritmo, que se da en la llamada recursiva de la l\'inea 18. Para hallar la ecuaci\'on de recurrencia para \texttt{solucion\_particion}, tuvimos que analizar el algoritmo con sumo detalle. Al ser recursivo, la complejidad por lo general es m\'as complicada de calcular y debe hacerse con mucho cuidado.

Llamaremos $n$ a la cantidad de nodos del grafo $g$. Como \texttt{solucion\_parcial} tiene, en cualquier corrida del algoritmo \texttt{solucion\_particion}, un tama\~no a lo sumo \texttt{tam\_part1}, entonces podemos acotarlo: $|solucion\_parcial| \leq tam\_part1$. Llamaremos entonces $p$ a $tam\_part1$. Luego nuestra ecuaci\'on de recurrencia quedar\'a dependiendo de los par\'ametros $n$ y $p$.

El algoritmo empieza agregando enteros del $1$ al $n$, en orden, sin repetidos, en el arreglo de entrada (con excepci\'on del primer elemento, que ya est\'a en el arreglo). Cuando llega a que su tama\~no es $p$, entra en un caso base, donde se determina (si se cumple la guarda del \texttt{if} de l\'inea 9) la soluci\'on que por ahora es la \'optima. En el paso inductivo, el algoritmo agrega y remueve elementos del arreglo, siempre desde el final, y vuelve a entrar en el caso base cuando nuevamente el arreglo tiene tama\~no $p$. La forma en que los elementos se van agregando y quitando permite obtener todas las posibles combinaciones de ciclos de $g$ con las caracter\'isticas vistas en la secci\'on \texttt{Algoritmo propuesto}.

La operaci\'on de remover (\texttt{remove}) un elemento al final del arreglo es constante (llamaremos $c$ a este costo), mientras que el agregado (\texttt{add}) junto con la b\'usqueda de un elemento en el arreglo (\texttt{contains}) tiene costo $p$, ya que el agregado es constante (amortizado) y la b\'usqueda se debe hacer, en peor caso, hasta el \'ultimo elemento de \texttt{solucion\_parcial}, que tiene tama\~no menor o igual que $p$. Por otro lado, si sumamos las complejidades de las operaciones de l\'ineas 6 a 14, obtenemos un tiempo en peor caso de $np + n + np$, que es $\mathcal{O}(np)$. Por \'ultimo, podemos ver que en cualquier corrida del algoritmo, podemos elegir de entre $n-p+k$ n\'umeros (o v\'ertices del grafo) para poner en la posici\'on $p-k$ de \texttt{solucion\_parcial}, para $1 \leq k \leq n-3$.

Dicho esto, tenemos la siguiente ecuaci\'on de recurrencia para el algoritmo \texttt{solucion\_particion}: \\

$$ T_{sol\_part}(n,p) = \sum_{k=0}^{n-3} \left( np + t_k \right) = \sum_{k=0}^{n-3} np + \sum_{k=0}^{n-3} t_k = (n-2) np + \sum_{k=0}^{n-3} t_k$$ \\

\newpage

donde $t_k$ es la siguiente sucesi\'on dada por recurrencia: \\ 

$$t_k = \left\{ 	
						    \begin{array}{c l} 
						  		 (n-p) (c+p+np) \; & \; k = 0 \\
							     (n-p+k) \left( t_{k-1} + (k+1) (c+p) \right) \; & \; k \geq 1 \\
	          	  \end{array} \right. $$


\small{\textbf{Explicaci\'on de la complejidad de \texttt{get2TSP}}}

Las cinco primeras l\'ineas del algoritmo corresponden a operaciones de tiempo constante. Dentro del ciclo de l\'ineas 12 a 25 se realizan todas operaciones de asignaci\'on, comparaci\'on, operaciones aritm\'eticas y llamadas a funciones de costo $\mathcal{O}(1)$, excepto en la l\'inea 15, donde se hace una llamada al m\'etodo recursivo \texttt{solucion\_particion}, al cual acabamos de calcular su complejidad. Entonces, la l\'inea 12 tiene una complejidad $T_{sol\_part}(n,tam\_part1)$, siendo $n$ la cantidad de nodos del grafo $g$. 

Por otro lado, el ciclo se ejecuta $\frac{n-5}{2} + 1$ veces si $n$ es impar, y $\lceil \frac{n-5}{2} \rceil$ si $n$ es par.

Por lo tanto, la complejidad total de \texttt{get2TSP} es: \\

$$T_{get2TSP}(n) = \left\{ 	
						    \begin{array}{c l} 
						  		 \sum_{j=1}^{\frac{n-5}{2} + 1} T_{sol\_part}(n,n-(j+1)) \;  & \; si \; n \; es \; impar \\
							     \sum_{j=1}^{\lceil \frac{n-5}{2} \rceil} T_{sol\_part}(n,n-(j+1)) \; &  \; si \; n \; es \; par \\
	          	  \end{array} \right.$$
	          	  
	          	  $$ \diamondsuit $$

$\linebreak$

Como vimos, el algoritmo exacto busca la soluci\'on \'optima y la encuentra para cualquier grafo dado que cumpla las hip\'otesis del problema 2-TSP. Sin embargo, al utilizar la t\'ecnica de fuerza bruta, realiza una b\'usqueda exhaustiva, pasando por todas las soluciones posibles del problema, lo que lo hace ineficiente si el grafo tiene muchos nodos (ya veremos en la secci\'on de \texttt{Resultados} de este algoritmo qu\'e significa ``muchos nodos'', o sea, cu\'al es el n\'umero m\'aximo aproximado de nodos que debe tener el grafo para que el algoritmo pueda terminar en un tiempo razonable). Y por lo tanto, la complejidad tanto para el mejor como para el peor caso es la misma. 


\subsection{Heur\'istica constructiva} 
\subsubsection*{Algoritmo propuesto}

Como su nombre lo indica, un m\'etodo constructivo consiste en ir armando la soluci\'on en cada paso del algoritmo. Se va agregando en cada iteraci\'on el mejor elemento de entre todos los posibles. 
Existen diversas t\'ecnicas constructivas. Para este problema se implement\'o una heur\'istica constructiva del vecino m\'as cercano. 

Inicialmente, as\'i como se explic\'o en la secci\'on del algoritmo exacto, se realizan distintas particiones posibles del grafo G. Estas particiones nos indican el tama\~no de los dos circuitos que van a tener las soluciones parciales del problema. De entre todas las soluciones parciales se toma la que tiene menor costo y \'esta ser\'a la soluci\'on final. Los costos se obtienen sumando cada uno de los pesos de las aristas pertenecientes a los dos ciclos.  \\

\begin{footnotesize}

\texttt{private Solucion get2TSP()}

\begin{algorithmic}[1]

\State solFinal = $Integer.MAX\_VALUE$;

\For{Cada particion posible  \texttt{p}}
	\State $solucion\_parcial = solucion\_golosa(p.tam1, p.tam2)$ \Comment{$\mathcal{O}(n^{2})$}	
	\State $solFinal = min\{solucion\_parcial, solFinal\}$	\Comment{$\mathcal{O}(1)$}				
\EndFor  \Comment{$\mathcal{O}(n)$}
		
\State return solFinal;
\end{algorithmic}

\end{footnotesize}

Para hallar los ciclos usaremos la t\'ecnica heur\'istica del vecino de menor costo. La implementaci\'on de la heur\'istica del vecino m\'as cercano utiliza el siguiente algoritmo:\\

\begin{footnotesize}
\texttt{private Solucion solucion\_golosa(int tam\_part1,int tam\_part2)}

\begin{algorithmic}[1]

\State $sol\_parcial = \{nodo\_orig\}$
\State $nodo\_anterior = \{nodo\_orig\}$
\State
\While{$|sol\_parcial| < tam\_part1$}
	\State $actual = menorPeso(anterior, sol\_parcial)$ \Comment{$\mathcal{O}(n)$}	
	\State $sol\_parcial = solucion\_parcial \cup \{actual\}$	\Comment{$\mathcal{O}(1)$}
	\State $anterior = actual$	\Comment{$\mathcal{O}(1)$}		
\EndWhile  \Comment{$\mathcal{O}(n^{2})$}
\State
\State $nodos\_visitados = sol\_parcial$
\State $sol\_parcial2 = \{nodo\_orig\}$
\State
\While{$sol\_parcial2 < tam\_part2$} 	
	\State $actual = menorPeso(anterior, nodos\_visitados)$ \Comment{$\mathcal{O}(n)$}	
	\State $sol\_parcial2 = solucion\_parcial2 \cup \{actual\}$	\Comment{$\mathcal{O}(1)$}
	\State $nodos\_visitados = nodos\_visitados \cup \{actual\}$	\Comment{$\mathcal{O}(1)$}
	\State $anterior = actual$	\Comment{$\mathcal{O}(1)$}		
\EndWhile  \Comment{$\mathcal{O}(n^{2})$}
\State
\State \texttt{return new} Solucion(sol\_parcial, sol\_parcial2);
\end{algorithmic}

\end{footnotesize}


\vspace{0.5cm}


Como se ve en el pseudoc\'odigo, una vez hallado el 1er ciclo, eso nos determina los nodos que estar\'an en el 2do ciclo. Pero estos, al ser un grafo completo, pueden tener muchas soluciones, por lo que para el complemento tambi\'en se busca la mejor soluci\'on golosa (lineas 10-18). Siempre se llega a una soluci\'on al ser un grafo completo de m\'as de 4 nodos. No podemos asegurar que la soluci\'on final obtenida sea la \'optima, ya que en cada iteraci\'on del algoritmo se elige el nodo que tenga la arista de menor peso, con lo que es posible que llegado al final del algoritmo por ejemplo, la ultima arista que queda determinada (que vuelve al primer nodo, nodo de origen) sea de un peso desorbitante. La ventaja de este algoritmo es su f\'acil implementaci\'on, explicaci\'on, y su baja complejidad temporal.   
  


\subsubsection*{Complejidad}

Ver todas las posibles particiones (l\'inea 2 del pseudoc\'odigo) es O(n) como vimos en la complejidad del algoritmo exacto. Dentro de cada iteraci\'on, se busca la soluci\'on golosa de esa partici\'on, lo cual requiere O($n^{2}$). De ser esto correcto, el ciclo (y as\'i el algoritmo en s\'i) tiene una complejidad de O(n * $n^{2}$) = O($n^{3}$). Veamos la complejidad de la funci\'on $\texttt{solucion\_golosa}$: Tenemos 2 whiles, cada uno itera a lo sumo n veces, y dentro del while, la \'unica operaci\'on que no es constante es el llamado a la funci\'on  $\texttt{menorPeso}$. Como dijimos anteriormente en la secci\'on Desarrollo, la funci\'on $\texttt{menorPeso(nodo\_anterior, nodos\_visitados)}$ devuelve el nodo vecino a ``nodo\_anterior'', que no est\'a en ``nodos\_visitados'', de menor costo. Esta funci\'on se realiza en O(n) ya que s\'olo se miran los vecinos del nodo, y al tener un acceso en O(1) a cada vecino (al estar implementado el grafo como una matriz), s\'olo se requieren O(n) operaciones. Lo \'unico que podr\'ia alterar esta complejidad es cuando se chequea si el nodo est\'a en ``nodos\_visitados''. Esto se puede realizar f\'acilmente en O(1) si la estructura de ``nodos\_visitados'' es un arreglo de booleanos (como la cantidad de nodos la sabemos de antemano, podemos crear este arreglo). De esta forma, el costo total de esta funci\'on es O(n) (para mayor detalles de las complejidades, recurrir al c\'odigo en Java). Entonces, la complejidad total de cada while es de O($n^{2}$) y por lo tanto, es la complejidad final de la funci\'on, resultando ser la complejidad final del algoritmo efectivamente O($n^{3}$).

\vspace{0.5cm}



\subsection{Heur\'istica de b\'usqueda local}
\subsubsection*{Algoritmo propuesto}
La heur\'istica de b\'usqueda local que implementamos para resolver el problema de 2-TSP tiene el siguiente algoritmo:

\begin{verbatim}
algoritmo get2TSP(Grafo G, Nodo v)
1.  Calcular una solucion inicial s* mediante la heuristica constructiva.
2.  Encontrar un s en N(s*) tal que c(s) < c(s*) 
3.  Si c(s) > c(s*) para todos los s en N(s*), parar. Si no, poner s*=s e ir al paso 2.      
\end{verbatim} 

Llamamos $N(s^*)$ a la \textit{vecindad} de $s^*$ y $c(x)$ a la funci\'on que calcula el peso total de una soluci\'on $x$. En breve explicaremos esto.

La heur\'istica constructiva devuelve una soluci\'on (aproximada) $s^*$, compuesta por dos ciclos simples que cubren todos los nodos del grafo $G$ y coinciden s\'olo en $v$. $N(s^*)$ contiene todos ciclos con estas caracter\'isticas que se pueden formar con los nodos de estos dos. M\'as precisamente, definimos la vecindad $N(s^*)$ de una soluci\'on $s^* = ({s^*}_1, {s^*}_2)$, donde ${s^*}_i$ representa cada ciclo de $s^*$, a las soluciones \textit{vecinas} de $s^*$ que pueden obtenerse:
\begin{itemize}
\item Intercambiando dos nodos de ${s^*}_1$
\item Intercambiando dos nodos de ${s^*}_2$
\item Intercambiando un nodo de ${s^*}_1$ con uno de ${s^*}_2$
\item Aplicando nuevamente estos intercambios a la soluci\'on que se obtiene as\'i: $$s^* = ({s^*}_1 - \{w\}, {s^*}_2 + \{w\}) \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \forall w \in {s^*}_1 \; \land \; w \neq v $$ suponiendo que ${s^*}_1$ tiene m\'as nodos que ${s^*}_2$. Es decir, aplicar los tres tipos de intercambio a la soluci\'on que se obtiene sacando un nodo de ${s^*}_1$ (que no sea el nodo $v$, el \'unico nodo que tienen en com\'un los ciclos de una particion 2-TSP(v)) y agreg\'andoselo a ${s^*}_2$, bajo la suposici\'on de que $|{s^*}_1| > |{s^*}_2|$, que siempre ocurre en nuestro algoritmo (ya se ver\'a en el c\'odigo Java).
\end{itemize} 

El algoritmo busca una soluci\'on $s$ en $N(s^*)$ que verifique $c(s) < c(s^*)$, donde $c(x)$, la funci\'on \textit{costo} es la suma de los pesos totales de los dos ciclos de $x$. Si esto se cumple, se determina que se ha ``mejorado'' la mejor soluci\'on hallada por el momento $(s^*)$, y entonces se vuelve a calcular la vecindad para esta nueva soluci\'on (paso 2). El algoritmo termina cuando ninguna de las soluciones vecinas (las que est\'an en $N(s^*)$) tiene un costo menor que $s^*$, y por lo tanto se devuelve $s^*$ como soluci\'on final, ya que no puede mejorarse m\'as. 

Ahora, ?`por qu\'e nuestro algoritmo de b\'usqueda local es correcto y termina? Primero veamos que termina.

Consideremos la soluci\'on inicial $s*$ y su vecindad $N(s^*)$. Podemos particionar a $N(s^*)$ en las soluciones vecinas que tienen costo menor que $s^*$ (o sea son soluciones mejores que $s^*$) y las que tienen costo mayor o igual que $s^*$ (soluciones peores que $s^*$). Entonces, tenemos que: $$N(s^*) = N_{mejor}(s^*) \cup N_{peor}(s^*) $$ donde $N_{mejor}(s^*) = \{ s \in N(s^*) \; / \; c(s) < c(s^*) \} $ y $N_{peor}(s^*) = \{ s \in N(s^*) \; / \; c(s) \geq c(s^*) \}$

Si $N_{mejor}(s^*) = \emptyset$, entonces $s^*$ es la mejor soluci\'on, y entonces el algoritmo termina ya que $s^*$ no puede mejorarse m\'as. Si no ocurre esto, entonces tenemos al menos una soluci\'on $s$ vecina de $s^*$ que es ``mejor'' que \'esta. Por lo tanto, cuando encontremos esta soluci\'on, volveremos al paso 2 y ahora tendremos la nueva vecindad $N(s)$. Si ahora encontramos una soluci\'on en $N(s)$ mejor que $s$, habremos conseguido nuevamente obtener una de menor costo. En el peor caso, llegamos a una soluci\'on de costo 6 (el peso m\'inimo que puede tener una particion 2TSP(v)), y entonces ninguna otra soluci\'on vecina puede tener costo menor; entonces, el algoritmo para. Tambi\'en podr\'ia parar cuando ninguna de las soluciones vecinas tiene costo menor a la actual.

Entonces, llegar\'a un momento en que $N_{mejor}(s') = \emptyset$ para alguna soluci\'on $s'$, y entonces, como vimos al principio, el algoritmo termina, devolviendo esta soluci\'on $s'$, ya que su vecindad contiene todas soluciones peores que \'esta. 

Luego el algoritmo de b\'usqueda local \texttt{get2TSP} termina, y es correcto ya que devuelve una soluci\'on que se aproximar\'a a la soluci\'on \'optima del problema.


\subsubsection*{Complejidad}

\textbf{Peor caso}

A continuaci\'on analizamos la complejidad en peor caso del algoritmo de b\'usqueda local. El c\'odigo Java del m\'etodo que implementa este algoritmo es nuevamente \texttt{get2TSP}, de la clase \textsc{BusquedaLocal}. \\


\begin{footnotesize}
\texttt{private Solucion get2TSP()}

\begin{algorithmic}[1]

\State $constructiva = new \;  Constructiva(getG()); $ 	 \Comment{$\mathcal{O}(1)$}	
\State $Solucion \; mejorSol = constructiva.get2TSP(); $ \Comment{$\mathcal{O}(n^3)$}		
%\State $int tolerancia = toleranciaOriginal; $		
		
\Repeat{
\State $ ArrayList<Integer> \; vecina2, vecina1;$	\Comment{4-8: $\mathcal{O}(1)$}
\State $int \; tamPart1 = mejorSol.getCiclo1().size(); $		
	\State $int \; tamPart2 = mejorSol.getCiclo2().size(); $	
	\State $ int \;  max, maxOriginal, costoVecina, temp;$		
	\State $boolean \; encontreMejorSolucion = false; $		
	\State $Solucion \; mejorSolOriginal = new \; Solucion((ArrayList<Integer>) \; mejorSol.getCiclo1().clone(), \linebreak (ArrayList<Integer>) \; mejorSol.getCiclo2().clone(), mejorSol.getCosto()); $	 \Comment{$\mathcal{O}(n)$}	
	\State $Solucion \; vecina = null; $	\Comment{$\mathcal{O}(1)$}
			
	\If{$(tamPart1 < tamPart2)$} \Comment{11-21: $\mathcal{O}(1)$}
		\State $	max = tamPart2; $		
		\State $	maxOriginal = tamPart2;$			
		\State $temp = tamPart1; $			
		\State $	tamPart1 = tamPart2;$		
		\State $ tamPart2 = temp;$			
		\State $ mejorSol.cambiarCiclos();$			
	\Else
		\State $max = tamPart1; $			
		\State $maxOriginal = tamPart1; $			
    \EndIf
	
	\For{$(int\;  k = 0; k < maxOriginal - 2;k++)$} 	\Comment{Cicla $maxOriginal-2$ veces}	
		
		\For{$(int \; i = 1; i < max; i++)$} \Comment{Cicla $max-1$ veces}
				
			\For{$(int  \; j = 1; j < max; j++)$}{ \Comment{$\mathcal{O}(n^2) $}	 
					
				\State $ vecina1 = mejorSol.getCiclo1();$		 \Comment{25-33: $\mathcal{O}(1)$}		
				\State $ vecina2 = mejorSol.getCiclo2();$				
						
			 	\If{$(vecina1.size() < vecina2.size())$}						
					\State $ArrayList<Integer> \; vecinaTemp = vecina1; $					
					\State $ vecina1 = vecina2;$					
					\State $ vecina2 = vecinaTemp;$				
					\State $tamPart1 = vecina1.size(); $					
					\State $tamPart2 = vecina2.size(); $					
				\EndIf
						
				\If{$(i \neq j)$}
		
					\If{$(i < tamPart2 \; \land \; j < tamPart2)$}
								
						\State $ swap(vecina2,i,j);$							
						\State $ costoVecina = g.calcular\_costo(vecina1) + g.calcular\_costo(vecina2);$	  \Comment{$\mathcal{O}(n)$}					
									
						\If{$(costoVecina < mejorSol.getCosto())$}
									
							\State $ vecina = new \; Solucion(vecina1,vecina2,costoVecina);$	  \Comment{$\mathcal{O}(|vecina1|)$}								
							\State $ encontreMejorSolucion = true;$						
							\State $ break; $							
						\Else{
							\State $ swap(vecina2,j,i);$							
						}\EndIf
			
					\EndIf
								
					\If{$(i < tamPart1 \; \land \; j < tamPart1)$}
								
						\State $swap(vecina1,i,j); $							
						\State $ costoVecina = g.calcular\_costo(vecina2) + g.calcular\_costo(vecina1);$  \Comment{$\mathcal{O}(n)$}			
									
						\If{$(costoVecina < mejorSol.getCosto())$}		
							\State $vecina = new \; Solucion(vecina1, vecina2,costoVecina); $  \Comment{$\mathcal{O}(|vecina1|)$}							
							\State $encontreMejorSolucion = true; $							
							\State $break; $							
						\Else{						
							\State $swap(vecina1,j,i); $								
						}
						\EndIf
					\EndIf
				\EndIf
						
				\If{$(j < tamPart1 \; \land \; i < tamPart2)$} 
					\State $swap(vecina1,vecina2,i,j); $			
					\State $costoVecina = g.calcular\_costo(vecina1) + g.calcular\_costo(vecina2); $	 \Comment{$\mathcal{O}(n)$}					
					
					\If{$(costoVecina < mejorSol.getCosto())$}
						\State $vecina = new Solucion(vecina1, vecina2,costoVecina);$	  \Comment{$\mathcal{O}(|vecina1|)$}			
						\State $encontreMejorSolucion = true; $					
						\State $break; $				
					\Else
						\State $swap(vecina1,vecina2,i,j); $		
					\EndIf
				\EndIf
						
			}\EndFor
					
			\If{$(encontreMejorSolucion)$}
				\State $ mejorSol = vecina;$			
				\State $break; $			
			\EndIf

		\EndFor
				
		\If{$(encontreMejorSolucion)$}	
			\State $mejorSol = vecina; $			
			\State $break; $		
		\EndIf

		\State $ ArrayList<Integer> \; ciclo1 = mejorSol.getCiclo1();$		
		\State $ArrayList<Integer> \;  ciclo2 = mejorSol.getCiclo2(); $		
		\State $Integer \; t = ciclo1.get(1); $		\Comment{$\mathcal{O}(1)$}	 
		\State $ ciclo1.remove(1);$		  \Comment{$\mathcal{O}(|ciclo1|)$}	 
		\State $ciclo2.add(t);$		 \Comment{$\mathcal{O}(1)$, amortizado}	 
		\State $ tamPart1 = ciclo1.size();$		
		\State $ tamPart2 = ciclo2.size();$		

	\EndFor %cierra for k=0 etc...
	
	\If{$(encontreMejorSolucion)$}
		\State $encontreMejorSolucion = false; $			
	\Else
		\State $mejorSol = mejorSolOriginal; $			
		\State $break; $			
	\EndIf
}\Until{(true);}
	\State $return \; mejorSol; $	
\end{algorithmic}

\end{footnotesize}

$\newline$

Las l\'ineas que no est\'an comentadas corresponden a operaciones de tiempo constante, o sea son $\mathcal{O}(1)$. En la l\'inea 2 se llama al algoritmo \texttt{get2TSP} de la versi\'on constructiva, que toma tiempo $\mathcal{O}(n^3) $. En la l\'inea 9 se hace una llamada al m\'etodo \texttt{clone}, que copia los dos ciclos de la soluci\'on \textit{mejorSolOriginal}, lo cual toma tiempo lineal en la cantidad de elementos de cada uno, en total, $n+1$. Luego esta l\'inea es $\mathcal{O}(n) $. De ah\'i en m\'as hasta la l\'inea 21 se hacen operaciones en tiempo constante.

El ciclo \texttt{for} exterior (l\'ineas 22 a 86) se ejecuta a lo sumo $maxOriginal-2$ veces, cantidad que podemos acotar superiormente por $n-2$ (ya que $maxOriginal$ es el tama\~no de uno de los ciclos de la soluci\'on, el cual es siempre menor o igual a $n-2$). A su vez, $n-2 < n$. El ciclo anidado (l\'ineas 23 a 74) cicla a lo sumo $max-1$ veces. Nuevamente, podemos acotar esto: $max-1<n-1<n$.

Entre las l\'ineas 25 y 33 tenemos operaciones en $\mathcal{O}(1)$ y entre las 34 y 69 hay operaciones que en total tienen una complejidad $\mathcal{O}(n+|vecina1|)$. Pero como $|vecina1|$ tiene tama\~no a lo sumo $n-2$, entonces esta complejidad se puede escribir como $\mathcal{O}(n+n-2) = \mathcal{O}(n)$. Por lo tanto, el costo del ciclo anidado (l\'ineas 24 a 69) es $\mathcal{O}(max*n) = \mathcal{O}(n^2)$, ya que $max \leq n-2$. 

Luego la complejidad total del ciclo \texttt{for} exterior es $\mathcal{O}((n^3+n)*n) = \mathcal{O}(n^4+n^2) = \mathcal{O}(n^4)$. 

La complejidad final de \texttt{get2TSP} es: $\mathcal{O}(C * (n + n^4) + n^3) = \mathcal{O}(C * n^4 + n^3 ) = \mathcal{O}(C * n^4 )$, donde la variable $C$ es cuantas veces se encontro una mejor solucion en la vecindad, es decir, cuanto se ejecuta el \texttt{repeat...until}.  \\ 


\textbf{Mejor caso}

En el mejor caso, la heur\'istica constructiva nos da la mejor soluci\'on $s*$ del problema. Es decir, ninguna soluci\'on $s \in N(s*)$ tiene costo menor a $s*$. Entonces el \texttt{do...while} s\'olo se ejecuta una vez, y por tanto, tiene una complejidad $ \mathcal{O}(n^4 + n^3 ) =  \mathcal{O}(n^4)$


\subsection{Metaheur\'istica Tab\'u Search}
\subsubsection*{Algoritmo propuesto}

Para la metaheuristica Tabu Search, nos basamos en el algoritmo de Busqueda Local pero con algunos agregados. Primero y principal, ahora vamos a permitir que en ciertas ocasiones, la nueva solucion tenga un costo mayor al de la solucion anterior. Es decir, en cada iteracion tomamos como nueva solucion a $s^*$, buscamos un $w \in {N(s^*)} /$ $\forall v \in {N(s^*)},$ $costo(w) \leq costo(v)$, por lo que en ciertas ocasiones puede pasar que el costo de la nueva solucion w sea mayor que el costo de $s^*$. De esta manera, estamos permitiendo tomar un rango mayor de soluciones, y, si caemos en un optimo local, poder ``escaparnos'' de el. Una vez agregado esto, implementamos la lista Tabu, la cual guarda caracteristicas de la solucion para no caer en ella rapidamente y entrar en un posible ciclo. Para esto, nosotros nos guardamos los nodos que intercambiamos en cierta iteracion. De esta manera, el siguiente intercambio de esos nodos no se va a efectuar porque esta en la lista Tabu, y no se va a poder producir el ciclo. Ademas, cada par de nodos que se intercambian y se agregan a la lista Tabu, tienen un contador el cual se disminuye en cada iteracion en una unidad. Este contador se setea pasandolo como 1er parametro a la funcion   $\texttt{get2TSP(int t, int toleranciaOriginal, int iterD\_param)}$. Ademas de este contador (o tiempo de expiracion), tenemos 2 parametros mas en la nueva funcion comparado a $\texttt{BusquedaLocal}$: toleranciaOriginal, y iterD\_param. La tolerancia nos dice cuantas veces iteramos desde que la solucion hallada no fue mejorada. Esto es ya que, puede ser que haya entrado en un ciclo largo (osea, cada una cantidad de iteraciones, las soluciones se empiezan a repetir) o que se haya llegado al optimo local, y no haya una solucion mejor. Sin esto, el algoritmo nunca dejaria de ciclar y por lo tanto nunca terminaria. Por otro lado, la variable iterD\_param nos dice cuantas veces nos permitimos usar diversificacion en el algoritmo. Que es usar diversificacion?. Es permitirnos, siempre y cuando no hay una solucion mejor en la vecindad y la tolerancia haya llegado a 0, es tomar una solucion ``muy'' diferente a las que estabamos analizando, de forma tal de no seguir cayendo en el mismo optimo local, y permitirnos caer en otro optimo local, o si dios quiere, en el optimo global. Para esto, lo que hacemos es ir guardandonos en una estructura llamada Memo, en la cual nos guardamos, para cierta particion, cuantas veces estuvo cada elemento en cierta posicion dentro del ciclo. De esta forma, cuando queremos ``diversificar'' la solucion, primero miramos cual fue la particion que menos veces se analizo, y posteriormente, una vez fijado el tama\~n de cada particion, lo que hacemos es ir poniendo en cada posicion el elemento que aparecio menos veces en esa posicion (y que sea posible, ya que no pueden haber nodos repetidos en el ciclo). Aunque de todas formas podriamos terminar eligiendo una solucion que ya la hayamos analizado, esto sucederia con probabilidad muyy baja y por otro lado, ir guardandonos todas las soluciones que miramos, y cuando llega la hora de diversificar, tomar una solucion cualquiera que no la hayamos analizado seria impracticable ya que serian muchisimas las soluciones a guardar, por lo que se volveria algo muy lento despues de unas iteraciones.

%describir instancias de 2-TSP donde el metodo no proporciona una solucion optima ¿Que tan mala puede ser la sol obtenida respecto de la optima?


\subsubsection*{Complejidad}

La complejidad es similar a la de busquedaLocal, pero con unas peque\~nas variantes: Primero que nada el \texttt{repeat...until} es reemplazado con la condicion de que itera hasta la tolerancia indicada por parametro (O(tolerancia)). Ademas, este \texttt{repeat...until} esta dentro de otro ciclo que itera la cantidad de diversificaciones que se producen ( O(diversificaciones)). Veamos un poco mas en detalle el ciclo que itera hasta la tolerancia. Este ciclo es equivalente al ciclo \texttt{repeat...until} del algoritmo de BusquedaLocal salvo peque\~nas diferencias. La unica importante que podria afectar la complejidad, es cuando chequeamos si el intercambio a realizar esta en la listaTabu. Para esto, tenemos que recorrer los elementos de esta lista. Como los elementos en la lista Tabu duran hasta el tiempo de Expiracion, el tiempo de expiracion decrece en una unidad en cada iteracion, y ademas, se agrega un unico elemento en cada iteracion, el tama\~no maximo de esta lista es O(tiempoExpiracion). Por lo tanto, como este chequeo se hace en el ultimo for anidado (y son 3 for's anidados) la complejidad queda en O($n^{3}$ * tiempoExpiracion) para esos chequeos de si el intercambio es posible o no lo es porque esta en la lista Tabu. Ademas, como vimos para el algoritmo de BusquedaLocal, tenemos O($n^{4}$) operaciones. Por lo tanto, la complejidad del ciclo en cuestion nos queda en: O(tolerancia * ($n^{3}$ * tiempoExpiracion + $n^{4}$)) y la complejidad final queda en O(diversificaciones * tolerancia * ($n^{4}$ + $n^{3}$ * tiempoExpiracion)). Si consideramos que las variables diversificaciones, tolerancia y tiempoExpiracion son constantes (como veremos en la seccion Resultados, no hacen falta valores muy altos para estas variables), la complejidad queda en O($n^{4}$). En el codigo Java, se encuentran comentadas las lineas con su complejidad que modifican la complejidad del algoritmo con respecto a busquedaTabu para un mayor detalle.

\newpage

\section{Resultados}


%aplicar el metodo a varias instancias de 2-TSP. Para tabu, analizar con distintas tolerancias y tiempos de expiracion 

%describir instancias de 2-TSP donde el metodo no proporciona una solucion optima.

Primero comenzamos experimentando con la tolerancia para buscar un valor acorde. Es decir, un valor muy alto puede hacer costoso el rendimiento del algoritmo al tener que hacer tantas iteraciones, capaz sin sentido ya que el m\'inimo ya fue hallado, o porque entro en un ciclo largo (el algoritmo est\'a ciclando en una sucesi\'on de posibles soluciones a analizaro). Un valor muy bajo podr\'ia hacer que la soluci\'on hallada estuviera algo alejada del \'optimo, y si hubi\'eramos tenido una tolerancia mayor, podr\'ia ocurrir que se hallara una soluci\'on m\'as cercana a la \'optima. Dicho esto, comenzamos teniendo una intuici\'on de que un valor de 1000 podr\'ia ser un buen valor por defecto. De esta forma, al ir experimentando con grafos al azar nos dimos cuenta que nunca se tardaba ni cerca de la mitad de las iteraciones hasta que se ``estancaba'' en una soluci\'on, y en cambio, en menos de 100 iteraciones casi siempre se llegaba a la soluci\'on del algoritmo. Como consecuencia, realizamos un algoritmo que generaba 10 grafos de tama\~no 5, 10 grafos de tama\~no 6, y as\'i sucesivamente hasta 10 grafos de tama\~no 30, y para cada grafo, nos dec\'ia cuando la soluci\'on hallada no se modificaba m\'as despu\'es de tal iteraci\'on (tomando como tolerancia m\'axima igual a 1000). A continuaci\'on, presentamos los datos obtenidos:

\vspace{0.5cm}

\begin{tikzpicture}
\begin{axis}[ybar interval,
xtick=data,
enlargelimits,
nodes near coords,
xticklabel interval boundaries,
ylabel = cant. soluciones halladas,
xlabel = tol,
x tick label style=
{rotate=90,anchor=east}
]
\addplot coordinates
{(0,229) (50,17) (100,3) (150,1) (200,0)};
\end{axis}
\end{tikzpicture}

Como vemos, en la mayor\'ia de los casos la soluci\'on despu\'es de la iteraci\'on 50 no se modifica m\'as durante las 950 iteraciones restantes (recordemos que tomamos 1000 iteraciones en total). Entre 150 y 200 iteraciones, s\'olo obtuvimos 1 grafo en 250 grafos, con lo cual podemos ver que la probabilidad de que despu\'es de 200 iteraciones la soluci\'on se modifique es baj\'isima.

\vspace{0.5cm}

Realizamos este mismo experimento varias veces, y el peor caso hallado fue solamente el de un grafo en el cual se tardaba entre 200 y 250 iteraciones para hallar una soluci\'on, y despu\'es entre las iteraciones 250 a 1000 no se modificaba la soluci\'on hallada. De esta manera, llegamos a la conclusi\'on de que un buen valor para la tolerancia ser\'ia el doble de lo m\'aximo que alcanzamos, por lo tanto, redujimos la tolerancia por defecto de 1000 a 300 (adem\'as, para no abusar con la cantidad de iteraciones y hacerlo un poco mas \'agil al algoritmo, ya que como veremos mas adelante, resulta algo lento comparado con los demas en la practica).

\vspace{0.5cm}

Posteriormente, tratamos de analizar al par\'ametro que nos permite cambiar el tiempo de expiraci\'on de los elementos de la lista tab\'u. Al haber escuchado en la te\'orica que un buen valor para ello ser\'ia algo as\'i como entre 5 y 10, experimentamos cambiando el tiempo de expiraci\'on en un rango del 1 al 15. C\'omo nos podr\'ia afectar el tiempo de expiraci\'on? Si el tiempo de expiraci\'on es muy bajo, podr\'iamos entrar en ciclos r\'apidamente, por lo que no encontrar\'ia mejores soluciones. Si el tiempo de expiraci\'on es alto, hay varios movimientos que no vamos a tener en cuenta a la hora de realizar intercambios, por lo que estar\'iamos restringiendo el espacio de soluciones a hallar. Para realizar este experimento, tomamos 10 grafos al azar de tama\~no 20, 10 grafos al azar de tama\~no 21, y as\'i sucesivamente hasta 10 grafos al azar de tama\~no 30. Los resultados obtenidos fueron los siguientes:

\vspace{0.5cm}

\begin{tikzpicture}
\begin{axis}[ybar,
xtick=data,
nodes near coords,
ylabel = cant. soluciones halladas,
xlabel = tiempo de Expiracion
]
\addplot coordinates
{(0,2) (1,2) (2,3) (3,4) (4,8) (5,13) (6,12) (7,15) (8,9) (9,9) (10,10) (11,7) (12,3) (13,3) (14,2)};
\end{axis}
\end{tikzpicture}

\vspace{0.5cm}

Efectivamente vemos como con tiempos de expiraci\'on entre 5 y 10 el algoritmo obtiene mejores soluciones en general. La mayor cantidad de mejores soluciones se obtienen con un tiempo de expiraci\'on igual a 7 (de los 100 grafos testeados, 15 grafos obtuvieron la mejor soluci\'on tomando tiempo de expiraci\'on igual a 7), no muy lejos de los tiempos de expiraci\'on 5 (13 grafos) y 6  (12 grafos). De este modo, seteamos como tiempo de expiraci\'on por defecto el valor 7.

\vspace{0.5cm}

Por \'ultimo, nos falta analizar c\'omo cambia la soluci\'on con diversificaci\'on. Para diversificaci\'on tomamos 10 grafos al azar de tama\~no 20, 10 grafos al azar de tama\~no 21, y as\'i sucesivamente hasta 10 grafos de tama\~no 25. Obtuvimos los siguientes resultados:

\vspace{0.5cm}

\begin{tikzpicture}
\begin{axis}[ybar,
xtick=data,
nodes near coords,
ylabel = cant. soluciones halladas,
xlabel = cant. de diversificaciones
]
\addplot coordinates
{(0,16) (1,9) (2,8) (3,6) (4,5) (5,6) (6,6) (7,2) (8,2) (9,0) (10,0)};
\end{axis}
\end{tikzpicture}

\vspace{0.5cm}

En el eje x tenemos cu\'antas veces aplicamos diversificaci\'on. De los 60 grafos analizados, vemos que 16 veces no fue necesaria aplicar diversificaci\'on ya que obtuvimos la mejor soluci\'on del algoritmo en la 1era iteraci\'on, y en las iteraciones restantes la soluci\'on del algoritmo no cambi\'o. Por otro lado, m\'as de la mitad de las veces (73\% de las veces) el resultado con diversificaci\'on fue mejor. Cu\'antas veces es necesario aplicar diversificaci\'on, sin hacer muy costoso el algoritmo y que nos permite acercarnos al valor \'optimo? Como se ve en el gr\'afico, mientras m\'as diversificaciones, menos probabilidad hay de encontrar una soluci\'on mejor. De esta forma, vemos c\'omo a partir de 8 diversificaciones, ya no se encuentran nuevas soluciones para los grafos analizados. Por lo tanto, concluimos de que un n\'umero de veces igual a 8 para el par\'ametro de diversificaci\'on es acorde para el algoritmo.

A continuacion, mostramos los tiempos de ejecucion obtenidos para grafos generados al azar, de tama\~no entre 10 y 50 nodos.
\begin{figure}[here]
\begin{tikzpicture}
    \begin{axis}[
	axis x line=middle,
	xlabel=$n$,ylabel=t en ms
	]

\addplot[brown] table[x=n,y=t] {tableTiempos.txt};
\addplot[red,domain=0:50] {x^4/40};

\legend{BusquedaTabu, $x^{4}$/40}
\end{axis}
\end{tikzpicture}
\caption{Tiempos de ejecucion para grafos de distintos tama\~nos con BusquedaTabu. Valores usados: tolerancia = 300, tiempoExpiracion = 7, diversificaciones=8}
\label{BusquedaTabu}
\end{figure}


\begin{figure}[here]
\begin{tikzpicture}
    \begin{axis}[
	axis x line=middle,
	xlabel=$n$,ylabel=t en ms
	]


\addplot[blue] table[x=n,y=tl] {tableTiempos2.txt};
\addplot[green] table[x=n,y=tc] {tableTiempos2.txt};
\addplot[black,domain=0:50] {x^4/50000};
\addplot[red,domain=0:50] {x^3/8000};

\legend{BusquedaLocal, Constructiva, $x^{4}$/50000,$x^{3}$/8000}
\end{axis}
\end{tikzpicture}
\caption{Tiempos de ejecucion para grafos de distintos tama\~nos con BusquedaLocal y Constructiva}
\label{BusquedaTabu}
\end{figure}

Como vemos en el grafico, las curvas de los tiempos son las esperadas, aunque con una constante mucho mayor para la version de BusquedaTabu con respecto al de BusquedaLocal

\newpage

\section{Conclusiones}
\begin{itemize}
\item La metaheur\'istica de B\'usqueda Tab\'u, con la t\'ecnica de diversificaci\'on, es la ``mejor" de entre todas las heur\'isticas implementadas, en t\'erminos de la calidad de la soluci\'on que devuelve. Esto es porque a medida que avanza la b\'usqueda va aceptando soluciones no tan buenas (lejos de ser \'optimas) para no estancarse en un m\'inimo local y salir r\'apido. Sin embargo, resulta ser un m\'etodo m\'as lento, al abarcar y analizar un rango mayor de soluciones que las otras heur\'isticas.

\item Hay casos donde la heur\'istica constructiva implementada no da la mejor soluci\'on, como es el caso de la tercera instancia del archivo \texttt{Tp3.in}, donde tenemos un grafo de 6 nodos, donde s\'olo una arista tiene un peso muy distinto a las otras, que tienen pesos parecidos. En este caso, como se puede ver en el archivo de salida generado por \texttt{ConstructivaTest.java} para esta instancia, el costo de la soluci\'on es 209, mientras que si ejecutamos el algoritmo exacto, vemos que la soluci\'on \'optima es 14, o sea con la constructiva obtenemos una soluci\'on p\'esima.

\item El hecho de partir de una soluci\'on inicial (dada por la heur\'istica constructiva) permite que tanto en la b\'usqueda local como en la b\'usqueda tab\'u se llegue a una soluci\'on aproximada mejor que \'esta. Es por eso que estos dos m\'etodos se pueden considerar superiores a la constructiva, aunque tienen una complejidad un poco mayor.
\end{itemize}


\newpage

\section{Referencias}

\begin{thebibliography}{99} 
\bibitem{java} JavaTM 2 Platform, Standard Edition, v 1.4.2 API Specification (http://docs.oracle.com/javase/1.4.2/docs/api/)


\end{thebibliography}

\end{document}


